package eashrine;

import java.util.ArrayList;
import java.util.List;

/**
 * @Author: Siantar
 * @Date: 2023-07-17-22:15
 * @Description: 1.0
 */
public class T0037 {
    public boolean[][] line = new boolean[9][9];
    public boolean[][] column = new boolean[9][9];
    public boolean[][][] block = new boolean[3][3][9];
    public boolean valid = false;
    public List<int[]> spaces = new ArrayList<>();

    public void solveSudoku(char[][] board) {
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] == '.') {
                    spaces.add(new int[]{i, j});
                } else {
                    int digit = board[i][j] - '0' - 1;
                    line[i][digit] = column[j][digit] = block[i / 3][j / 3][digit] = true;
                }
            }
        }
        dfs(board, 0);
    }

    public void dfs(char[][] board, int pos) {
        if (pos == spaces.size()) {
            valid = true;
            return;
        }
        int[] space = spaces.get(pos);
        int x = space[0], y = space[1];
        for (int i = 0; i < 9 && !valid; i++) {
            if (!line[x][i] && !column[y][i] && !block[x / 3][y / 3][i]) {
                line[x][i] = column[y][i] = block[x / 3][y / 3][i] = true;
                board[x][y] = (char) (i + '0' + 1);
                dfs(board, pos + 1);
                line[x][i] = column[y][i] = block[x / 3][y / 3][i] = false;
            }
        }
    }
}
